LinHuijuan's Blog

数据处理算法

# 数据处理算法

[TOC]

# 一、数据渲染

# 1.1 一维数据的处理

// data.js
let datas = [
    {
        name: '第一周',
        children: [{
                name: '星期一',
                children: [{
                    name: '学习'
                }]
            },
            {
                name: '星期二'
            }
        ]
    },
    {
        name: '第二周',
        children: [{
                name: '星期一'
            }
    }
];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 1.1.1 方案一：简单遍历

  • Array.prototype.forEach()
let html = '';
datas.forEach(data => {
    html += `
        <li>${data.name}</li>
        `;
});
oList.innerHTML = html;
1
2
3
4
5
6
7

# 1.1.2 方案二：封装

  • Array.prototype.map()
//map()返回的是一个数组
oList.innerHTML = datas.map(data=>{
    return `<li>${data.name}</li>`;
}).join('');
1
2
3
4

​

# 1.2 多维数据的处理(无限级展示)

# 1.2.1 递归（注意循环条件的处理）

oList.innerHTML = createHTML(datas);

function createHTML(items) {

  return items.map(item =>{
      let str = `<li>${item.name}</li>`;

      if(Array.isArray(item.children)){
          str +=createHTML(item.children);
      }
      return str;
  }).join('');

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

  • 函数参数默认值

    • 样式美化

    • 第一种：空格&nbsp处理（存在兼容问题）

      oList.innerHTML = createHTML(datas);		
function createHTML(items, level = 0) {
    return items.map(item => {
        let s = '&nbsp;'.repeat(4 * level);
        let str = `<li>${s}${level} - ${item.name}</li>`;
        if (Array.isArray(item.children)) {
            // 不可以使用自增符号
            // 否则每一次调用函数都会level+1,使结构混乱
            str += createHTML(item.children, level + 1);
        }

        return str;
    }).join('');
}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14

    • 第二种：内联样式

      function createHTML(items, level = 0) {
    return items.map(item => {
        let str = `
					<li style="padding-left: ${level * 30}px">${level} - ${item.name}</li>
					`;

        if (Array.isArray(item.children)) {
            str += createHTML(item.children, level + 1);
        }

        return str;

    }).join('');
}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14

# 1.2.2 数组扁平化（降维）

使现有结构利于检索

# 1.2.2.1 简便方法：Array.prototype.flat(Infinity)

node环境下使用不了。

# 1.2.2.2 替代方案：使用reduce与concat

  • 方案一：反嵌套一层数组

    • 不能完全展开[1,[2,[3,4]]]

var arr1 = [1, 2, [3, 4]]; arr1.flat();

```js
arr1.reduce((acc, val) => acc.concat(val), []);// [1, 2, 3, 4]

// 或使用
const flatSingle = arr => [].concat(...arr);
1
2
3
4
5
  • 方案二：使用 reduce、concat 和递归无限反嵌套多层嵌套的数组
var arr1 = [1,2,3,[1,2,3,4, [2,3,4]]];

function flattenDeep(arr1) {
    return arr1.reduce((acc, val) => Array.isArray(val) ? acc.concat(flattenDeep(val)) : acc.concat(val), []);
}
flattenDeep(arr1);
// [1, 2, 3, 1, 2, 3, 4, 2, 3, 4]
1
2
3
4
5
6
7
  • 方案三：不使用递归，使用 stack 无限反嵌套多层嵌套数组
var arr1 = [1,2,3,[1,2,3,4, [2,3,4]]];
function flatten(input) {
    const stack = [...input];//stack.length:4
    console.log(stack.toString().split(',').map(Number));
    //[1, 2, 3, 1, 2, 3, 4, 2, 3, 4]
    const res = [];
    while (stack.length) {
        // 使用 pop 从 stack 中取出并移除值
        const next = stack.pop();
        if (Array.isArray(next)) {
            // 使用 push 送回内层数组中的元素，不会改动原始输入 original input
            stack.push(...next);
        } else {
            res.push(next);
        }
    }
    // 使用 reverse 恢复原数组的顺序
    return res.reverse();
}
flatten(arr1);// [1, 2, 3, 1, 2, 3, 4, 2, 3, 4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

  • 样式：添加checkbox

    let str = `
	<li style="padding-left: ${level*30}px">
	<input type="checkbox" ${item.checked ? 'checked':''}/>
	<span>${item.name}</span>
	</li>
	`;
    1
    2
    3
    4
    5
    6

# 二、数组扁平化

# 2.1 方案一：forEach()+递归

let newItems = flat(datas);
function flat(items) {
  let newArr = [];
  items.forEach(item => {
      newArr.push(item);
      if (Array.isArray(item.children)) {
          newArr = newArr.concat(flat(item.children));
      }
  });
  return newArr;
}
1
2
3
4
5
6
7
8
9
10
11

# 2.2 方案二：concat()+递归

function flat(items) {
  return items.reduce((prev, current) => {
      return prev.concat(current, Array.isArray(current.children) ? flat(current.children) : []);
  },[]);
}
1
2
3
4
5

  • 过滤需要的数据

    console.log(newItems.filter(item => item.checked));
    1

# 三、排序

  • Array.prototype.sort()
//list.js
let datas = [
    {
        chapter: 22,
        type: '客户端信息存储',
        title: 'cookie'
    },
    {
        chapter: 23,
        type: '前后端交互',
        title: 'XMLHttpRequest 对象'
    },
    {
        chapter: 22,
        type: '客户端信息存储',
        title: 'Application Cache'
    }
];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<!-- border改变的只是整个表格的最外框 -->
<table id="table" width="100%" border="1px" style="border-collapse:collapse">
    <thead>
        <tr>
            <th>章节</th>
            <th>类型</th>
            <th>知识点</th>
        </tr>
    </thead>
    <tbody></tbody>
</table>
1
2
3
4
5
6
7
8
9
10
11
let oTable = document.getElementById('table');
// tBodies 集合返回表格 <tbody> 元素的集合
let tbody = oTable.tBodies[0];

// 升序
datas.sort((a, b) => a.chapter - b.chapter);

tbody.innerHTML = createHTML(datas);
function createHTML(items){
    return items.map(item=>{
        return `
            <tr>
            <td>${item.chapter}</td>
            <td>${item.type}</td>
            <td>${item.title}</td>
            </tr>
            `
    }).join('');
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 四、数组去重

  • 测试模板

    // Array.from() 方法从一个类似数组或可迭代对象中创建一个新的数组实例。
let arr1 = Array.from(new Array(100000), (x, index) => {
    // console.log(x,index);//undefined ‘索引值’
    return index;
});
// console.log(arr1);
//返回0到100000-1的数组
let arr2 = Array.from(new Array(50000), (x, index) => {
    return index;
});
// getTime() 方法返回一个时间的格林威治时间数值。
//console.time('time');
let start = new Date().getTime();
function distinct(a, b) {
    //数组去重
}
console.log('去重后的长度', distinct(arr1, arr2).length);
//console.timeEnd('time'); //time:XXXms
let end = new Date().getTime();
console.log('耗时', end - start);
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20

# 4.1 双层for循环

let arr = a.concat(b);
let len = arr.length;
for (let i=0;i<len;i++){
    for(let j=i+1;j<len;j++){
        if(arr[i]==arr[j]){
            arr.splice(j,1);
            len--;
            j--;
        }
    }
}
return arr;
1
2
3
4
5
6
7
8
9
10
11
12

  • 耗时：13147

  • 兼容性好，占用内存较高，效率最低

# 4.2 filter()+indexOf()

let arr = a.concat(b);
return arr.filter((item, index) => {
  // indexOf检测元素在数组中第一次出现的位置是否和元素现在的位置相等
  // 如果不等则说明该元素是重复元素
  return arr.indexOf(item) === index;
})
1
2
3
4
5
6
  • 耗时：5958

# 4.3 for...of+includes()

let arr = a.concat(b);
let result = [];
for (let i of arr) {
  result.includes(i) || result.push(i);
}
return result;
1
2
3
4
5
6
  • 耗时：6095

# 4.4 sort()+排相邻重复项*

let arr = a.concat(b);
arr = arr.sort((a, b)=>{
  return a-b;
});
let len = arr.length;
let result = [arr[0]];
for(let i=1;i<len;i++){
  if(arr[i]!==arr[i-1]){
      result.push(arr[i]);
  } 
}
return result;
1
2
3
4
5
6
7
8
9
10
11
12
  • 耗时：12
let arr = a.concat(b);
arr = arr.sort();
let len = arr.length;
for(let i=1;i<len;i++){
    if(arr[i]===arr[i-1]){
        arr.splice(i,1);
        len--;
    } 
}
return arr;
1
2
3
4
5
6
7
8
9
10
  • 耗时：5253
  • splice()性能杀手，是O(n)，需要遍历n个元素

# 4.5 Objec(对象的属性不会重复)*

  • 虽然1和‘1’是不同的，但obj[1]===obj['1']，因为对象的键值只能是字符串。

  • typeof item + item拼成字符串作为key值

// typeof 1+1 //"number1"
// typeof '1'+'1' //"string1"
1
2

# 4.5.1 for...of+Object

let arr = a.concat(b);
let result = [];
let obj = {};
for (let i of arr) {
    if (!obj[i]) {
        result.push(i);
        obj[i] = 1;
    }
}
return result;
1
2
3
4
5
6
7
8
9
10
  • 耗时：10

# 4.5.2 filter()+Object

let arr = a.concat(b);
let obj={};
// filter()不会改变原有数组
return arr.filter((item)=>{
  if(!obj[typeof item+item]){
      obj[typeof item+item]=1;
      return true;
  }
})
1
2
3
4
5
6
7
8
9
  • 耗时：13
let arr1=[1,2,3];
let arr2=['1','2','3'];
console.log(distinct(arr1, arr2));//[1,2,3]
1
2
3

# 4.5.3 forEach+object

// 这个方法不适用于1、‘1’
let arr = a.concat(b);
let obj = {};
arr.forEach(item => {
  obj[item] = 1;
});
return Object.keys(obj).map(o=>Number(o));//将字符串数组转换成数组
1
2
3
4
5
6
7

耗时：19

# 4.6 new Set()*

  • Set的成员具有惟一性
return Array.from(new Set([...a,...b]));
// return [...new Set([...a,...b])]
1
2
  • 耗时：13
  • 用法：
let arr1 = [1,4,2,3,3,4,5];
let s1 = new Set(arr1);
let arr2 = [...s1];
1
2
3

# 4.7 特殊条件去重

还有一些特殊类型的去重（参考：https://juejin.im/post/5949d85f61ff4b006c0de98b）

方法 结果 说明
for循环 [1, "1", null, undefined, String, String, /a/, /a/, NaN, NaN] 对象和 NaN 不去重
indexOf [1, "1", null, undefined, String, String, /a/, /a/, NaN, NaN] 对象和 NaN 不去重
sort [/a/, /a/, "1", 1, String, 1, String, NaN, NaN, null, undefined] 对象和 NaN 不去重 数字 1 也不去重
filter + indexOf [1, "1", null, undefined, String, String, /a/, /a/] 对象不去重 NaN 会被忽略掉
filter + sort [/a/, /a/, "1", 1, String, 1, String, NaN, NaN, null, undefined] 对象和 NaN 不去重 数字 1 不去重
优化后的键值对方法 [1, "1", null, undefined, String, /a/, NaN] 全部去重
Set [1, "1", null, undefined, String, String, /a/, /a/, NaN] 对象不去重 NaN 去重

想了解为什么会出现以上的结果，看两个 demo 便能明白：

// demo1
var arr = [1, 2, NaN];
arr.indexOf(NaN); // -1
1
2
3

indexOf 底层还是使用 === 进行判断，因为 NaN ==== NaN的结果为 false，所以使用 indexOf 查找不到 NaN 元素

// demo2
function unique(array) {
   return Array.from(new Set(array));
}
console.log(unique([NaN, NaN])) // [NaN]
1
2
3
4
5

Set 认为尽管 NaN === NaN 为 false，但是这两个元素是重复的。

# 六、数组乱序

# 6.1 sort()

function randomSort(a,b) { 
    return .5 - Math.random(); 
}
1
2
3
  • 但这并不是真正的乱序，计算机的 random 函数因为循环周期的存在，无法生成真正的随机数。

# 6.2 洗牌算法

  • 标准：想要实现真正意义上的乱序，只要满足每个元素出现在各个位置的概率同等即可。

  • 思路：

    • 先从数组末尾开始，选取最后一个元素，与数组中随机一个位置的元素交换位置。
    • 然后在已经排好的最后一个元素以外的位置中，随机产生一个位置，让该位置元素与倒数第二个元素进行交换。
// 如果使用箭头函数，this指向的是全局函数
Array.prototype.shuffle = function() {
    let m = this.length, n;
    while (m) {
        n = (Math.random() * m--) << 0;	// 正数的向下取整操作
        [this[m], this[n]] = [this[n], this[m]]//ES6解构赋值
    }
    return this;
}
1
2
3
4
5
6
7
8
9

动态规划（DP算法）